#ifndef COMPOSE_H
#define COMPOSE_H

#endif // COMPOSE_H
#pragma once
#include "polygon.h"
#include <vector>
#include <set>
using namespace std;
struct combin_index {
    int com_1_index;
    int com_2_index;
    bool operator ==(const combin_index& p) const {
        if (p.com_1_index == this->com_1_index&&p.com_2_index == this->com_2_index) {
            return true;
        }
        return false;
    }
    bool operator <(const combin_index& p) const {
        int hash_this = this->com_1_index * 10 + this->com_2_index;
        int hash_p = p.com_1_index * 10 + p.com_2_index;
        if (hash_this < hash_p) {
            return true;
        }
        return false;
    }
};
class Assembled_rec : public rectangle {
public:
    polygon poly_outer;
    polygon poly_inner;
    bool if_success;
    bool if_better = false;
    double rate;
    double occu_rate;
    vector<rectangle> inserted_recs;
    vector<vector<int>> occu_map;
    void help_construct(const polygon& poly_outer, const polygon& poly_inner) {
        this->poly_outer = poly_outer;
        this->poly_inner = poly_inner;
        vector<pos> allpos;
        allpos.insert(allpos.end(), this->poly_outer.allVertrx.begin(), this->poly_outer.allVertrx.end());
        allpos.insert(allpos.end(), this->poly_inner.allVertrx.begin(), this->poly_inner.allVertrx.end());
        const rectangle& temp = polygon::get_rectangle(allpos);
        this->delayConstru(temp.x1, temp.y1, temp.x2, temp.y2);
    }
    Assembled_rec(const polygon& poly_outer, const polygon& poly_inner) {
        this->if_success = true;
        help_construct(poly_outer, poly_inner);
        double area_sum = 0;
        area_sum += polygon::get_rectangle(poly_outer.allVertrx).area;
        area_sum += polygon::get_rectangle(poly_inner.allVertrx).area;
        this->rate = this->area / area_sum;
        if (rate < 1) {
            this->if_better = true;
        }
        double occu_area = 0;
        occu_area += polygon::get_rec_area_sum(poly_outer);
        occu_area += polygon::get_rec_area_sum(poly_inner);
        this->occu_rate = occu_area / this->area;
    }
    Assembled_rec(const polygon& poly_outer) {
        this->if_success = true;
        this->poly_outer = poly_outer;
        this->rate = 1;
        const rectangle& temp = polygon::get_rectangle(poly_outer.allVertrx);
        this->delayConstru(temp.x1, temp.y1, temp.x2, temp.y2);
        double occu_area = 0;
        occu_area += polygon::get_rec_area_sum(poly_outer);
        this->occu_rate = occu_area / this->area;
    }
    Assembled_rec(const Assembled_rec& asb_rec) {
        this->if_success = asb_rec.if_success;
        this->if_better = asb_rec.if_better;
        this->rate = asb_rec.rate;
        this->index = asb_rec.index;
        this->occu_rate = asb_rec.occu_rate;
        this->poly_outer = asb_rec.poly_outer;
        this->poly_inner = asb_rec.poly_inner;
        this->inserted_recs = asb_rec.inserted_recs;
        this->occu_map = asb_rec.occu_map;
        this->delayConstru(asb_rec.x1, asb_rec.y1, asb_rec.x2, asb_rec.y2);
    }
    Assembled_rec &operator=(const Assembled_rec& asb_rec) {
        this->if_success = asb_rec.if_success;
        this->if_better = asb_rec.if_better;
        this->rate = asb_rec.rate;
        this->occu_rate = asb_rec.occu_rate;
        if (asb_rec.poly_inner.allVertrx.size() != 0 && asb_rec.poly_outer.allVertrx.size() != 0) {
            help_construct(asb_rec.poly_outer, asb_rec.poly_inner);
        }
        if (asb_rec.poly_inner.allVertrx.size() == 0 && asb_rec.poly_outer.allVertrx.size() != 0) {
            this->poly_outer = asb_rec.poly_outer;
            const rectangle& temp = polygon::get_rectangle(poly_outer.allVertrx);
            this->delayConstru(temp.x1, temp.y1, temp.x2, temp.y2);
        }
        return *this;
    }
    Assembled_rec() {
        this->if_success = false;
    }
    void write_file(fstream& file) {
        vector<pos> allpos;
        allpos.insert(allpos.end(), this->poly_outer.allVertrx.begin(), this->poly_outer.allVertrx.end());
        allpos.insert(allpos.end(), this->poly_inner.allVertrx.begin(), this->poly_inner.allVertrx.end());
        const rectangle& temp = polygon::get_rectangle(allpos);
        vector<rectangle> store_rec = this->inserted_recs;
        if ((((x2 - x1) != (temp.x2 - temp.x1)) && ((x2 - x1) == (temp.y2 - temp.y1))) && (((y2 - y1) != (temp.y2 - temp.y1)) && ((y2 - y1) == (temp.x2 - temp.x1)))) {
            clockwise_rotation_90(pos(temp.x1, temp.y1), poly_outer.allVertrx);
            clockwise_rotation_90(pos(temp.x1, temp.y1), poly_inner.allVertrx);
            clockwise_rotation_90(pos(temp.x1, temp.y1), allpos);
            for (int i = 0; i < inserted_recs.size(); i++) {
                vector<pos> rec_pos_vec = get_rec_all_pos(inserted_recs[i]);
                clockwise_rotation_90(pos(temp.x1, temp.y1), rec_pos_vec);
                inserted_recs[i] = polygon::get_rectangle(rec_pos_vec);
            }
        }
        const rectangle& temp_temp = polygon::get_rectangle(allpos);
        polygon::std_pos_vec(poly_outer.allVertrx, x1, y1, temp_temp.x1, temp_temp.y1);
        polygon::std_pos_vec(poly_inner.allVertrx, x1, y1, temp_temp.x1, temp_temp.y1);
        for (int i = 0; i < inserted_recs.size(); i++) {
            vector<pos> rec_pos_vec = get_rec_all_pos(inserted_recs[i]);
            polygon::std_pos_vec(rec_pos_vec, x1, y1, temp_temp.x1, temp_temp.y1);
            inserted_recs[i] = polygon::get_rectangle(rec_pos_vec);
            inserted_recs[i].init_inf=store_rec[i].init_inf;
        }
        write_polygon(file, poly_outer);
        if (poly_inner.allVertrx.size() != 0) {
            write_polygon(file, poly_inner);
        }
        for (int i = 0; i < inserted_recs.size(); i++) {
            inserted_recs[i].write_file(file);
        }
    }
    void write_polygon(fstream& file, const polygon& poly) {
        string result;
        result += "In Polygon:\n";
        result+=poly.init_inf+"\n";
        result += "Out Polygon:\n";
        for (int i = 0; i < poly.allVertrx.size(); i++) {
            result += "(" + to_string(poly.allVertrx[i].x) + "," + to_string(poly.allVertrx[i].y) + ")";
            if (i == poly.allVertrx.size() - 1) {
                result += "\n";
            }
        }
        file << result;
    }
    int get_occu_area() override {
        return this->occu_rate*this->area;
    }
    rectangle* get_copy()override {
        return new Assembled_rec(*this);
    }
    static vector<pos> get_rec_all_pos(const rectangle& rec) {
        return { pos(rec.x1,rec.y1),pos(rec.x2,rec.y1),pos(rec.x2,rec.y2),pos(rec.x1,rec.y2) };
    }
    static void clockwise_rotation_90(const pos& norm, vector<pos>& vec_pos) {
        for (int i = 0; i < vec_pos.size(); i++) {
            int ini_x = vec_pos[i].x;
            int ini_y = vec_pos[i].y;
            vec_pos[i].x = (ini_x - norm.x) * 0 - (ini_y - norm.y)*(-1) + norm.x;
            vec_pos[i].y = (ini_x - norm.x)*(-1) + (ini_y - norm.y) * 0 + norm.y;
        }
    }
    void do_process(){
        this->poly_outer.toRepr2();
        if(poly_inner.allVertrx.size()!=0)
            this->poly_inner.toRepr2();
    }
};

class compose
{
public:
    //装偶数个多边形
    static vector<polygon> allPolygon;
    //装所有的矩形看看能不能插入多边形拼接的空白处
    static vector<rectangle> allRectangle;
    //一组几个多边形
    static const int number_of_members = 8;
    //几次打乱后分组找最佳，次数越多效果越好.
    static const int number_of_shuffe =1;
    //获取偶数个多边形的最好拼接 返回值vector里装的Assembled_rec继承于rectangle
    static vector<Assembled_rec> testCompose() {
        Assembled_rec only_outer;
        if (allPolygon.size() % 2 == 1) {
            int rand_index = rand() % allPolygon.size();
            polygon outer = allPolygon[rand_index];
            outer.toRepr2();
            only_outer = Assembled_rec(outer);
            for (auto iter = allPolygon.begin(); iter != allPolygon.end(); iter++) {
                if (*iter == outer) {
                    allPolygon.erase(iter);
                    break;
                }
            }
        }
        vector<Assembled_rec> shuffled_best_asb_vec_all;
        int sand = 0;
        for (int try_time = 0; try_time < number_of_shuffe; try_time++) {
            srand((unsigned int)(time(0) + (sand++)));
            random_shuffle(allPolygon.begin(), allPolygon.end());
            vector<Assembled_rec> best_asb_vec_all;
            vector<vector<polygon>> grouped_poly;
            int count = 0;
            for (int m = 0; m < (allPolygon.size() / number_of_members); m++) {
                grouped_poly.push_back(vector<polygon>(allPolygon.begin() + count, allPolygon.begin() + count + number_of_members));
                count += number_of_members;
            }
            if (allPolygon.size() % number_of_members != 0) {
                grouped_poly.push_back(vector<polygon>(allPolygon.end() - (allPolygon.size() % number_of_members), allPolygon.end()));
            }
            for (vector<polygon>& poly_vec : grouped_poly) {
                for (polygon& poly : poly_vec) {
                    poly.std_pos_vec(poly.allVertrx, 0, 0);
                }
                vector<combin_index> group;
                vector<vector<combin_index>> allgroups;
                getgroups(allgroups, group, poly_vec.size());
                map<combin_index, Assembled_rec> memory_store;
                vector<Assembled_rec> best_asb_vec;
                for (int i = 0; i < allgroups.size(); i++) {
                    vector<Assembled_rec> result_vec;
                    for (int j = 0; j < allgroups[i].size(); j++) {
                        if (memory_store.find(allgroups[i][j]) != memory_store.end()) {
                            result_vec.push_back(memory_store[allgroups[i][j]]);
                        }
                        else {
                            Assembled_rec result = try_3_times(allgroups[i][j], poly_vec);
                            memory_store[allgroups[i][j]] = result;
                            result_vec.push_back(result);
                        }
                    }
                    if (i == 0) {
                        best_asb_vec.assign(result_vec.begin(), result_vec.end());
                    }
                    else {
                        if (if_all_true(best_asb_vec) == false) {
                            best_asb_vec.assign(result_vec.begin(), result_vec.end());
                        }
                        else {
                            if (if_all_true(result_vec) == true) {
                                if (get_asb_vec_areasum(best_asb_vec) > get_asb_vec_areasum(result_vec)) {
                                    best_asb_vec.assign(result_vec.begin(), result_vec.end());
                                }
                            }
                        }
                    }
                }
                best_asb_vec_all.insert(best_asb_vec_all.end(), best_asb_vec.begin(), best_asb_vec.end());
            }
            if (try_time == 0) {
                shuffled_best_asb_vec_all.assign(best_asb_vec_all.begin(), best_asb_vec_all.end());
            }
            else {
                if (if_all_true(shuffled_best_asb_vec_all) == false) {
                    shuffled_best_asb_vec_all.assign(best_asb_vec_all.begin(), best_asb_vec_all.end());
                }
                else {
                    if (if_all_true(best_asb_vec_all) == true) {
                        if (get_asb_vec_areasum(shuffled_best_asb_vec_all) > get_asb_vec_areasum(best_asb_vec_all)) {
                            shuffled_best_asb_vec_all.assign(best_asb_vec_all.begin(), best_asb_vec_all.end());
                        }
                    }
                }
            }
        }
        if (only_outer.if_success == true) {
            shuffled_best_asb_vec_all.push_back(only_outer);
        }
        return shuffled_best_asb_vec_all;
    }

    static bool if_all_true(const vector<Assembled_rec>& result_vec) {
        for (const Assembled_rec& temp : result_vec) {
            if (temp.if_success == false) {
                return false;
            }
        }
        return true;
    }
    static void insert_rectangles(vector<Assembled_rec>& all_asb_rec) {
        for (Assembled_rec& temp_asb_rec : all_asb_rec) {
            init_occu_map(temp_asb_rec);
        }
        vector<rectangle> del_vec;
        for (int i = 0; i < allRectangle.size(); i++) {
            for (int j = 0; j < all_asb_rec.size(); j++) {
                if (try_insert(all_asb_rec[j], allRectangle[i]) == true) {
                    del_vec.push_back(allRectangle[i]);
                    break;
                }
            }
        }
        for (auto iter = allRectangle.begin(); iter != allRectangle.end();) {
            if (find(del_vec.begin(), del_vec.end(), *iter) != del_vec.end()) {
                iter = allRectangle.erase(iter);
            }
            else {
                iter++;
            }
        }
    }
    static bool try_insert(Assembled_rec& asb_rec, const rectangle& input_rec) {
        for (int i = asb_rec.x1; i <= asb_rec.x2; i++) {
            for (int j = asb_rec.y1; j <= asb_rec.y2; j++) {
                if ((i + 1 <= asb_rec.x2&&j + 1 <= asb_rec.y2) && asb_rec.occu_map[i + 1][j + 1] == 0) {
                    if (do_insert(pos(i, j), asb_rec, input_rec, input_rec) == true) {
                        return true;
                    }
                    else {
                        vector<pos> rota_90_vec_temp = { pos(input_rec.x2,input_rec.y2) };
                        pos norm = pos(input_rec.x1, input_rec.y1);
                        Assembled_rec::clockwise_rotation_90(norm, rota_90_vec_temp);
                        vector<pos> rota_90_vec = { norm,rota_90_vec_temp[0] };
                        if (do_insert(pos(i, j), asb_rec, polygon::get_rectangle(rota_90_vec), input_rec)) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
    static bool do_insert(const pos& insert_pos, Assembled_rec& asb_rec, const rectangle& input_rec, const rectangle& std_rec) {
        const int& trans_x2 = input_rec.x2 + (insert_pos.x - input_rec.x1);
        const int& trans_y2 = input_rec.y2 + (insert_pos.y - input_rec.y1);
        const int& trans_x1 = insert_pos.x;
        const int& trans_y1 = insert_pos.y;
        if (trans_x2 > asb_rec.x2 || trans_y2 > asb_rec.y2) {
            return false;
        }
        vector<vector<int>> occu_temp = asb_rec.occu_map;
        for (int i = trans_x1; i <= trans_x2; i++) {
            for (int j = trans_y1; j <= trans_y2; j++) {
                occu_temp[i][j]++;
            }
        }
        bool if_overlap = false;
        for (int i = trans_x1; i <= trans_x2; i++) {
            for (int j = trans_y1; j <= trans_y2; j++) {
                if (occu_temp[i][j] == 2) {
                    if ((i + 1 <= trans_x2 && j + 1 <= trans_y2) && occu_temp[i + 1][j + 1] == 2) {
                        if_overlap = true;
                    }
                }
            }
        }
        if (if_overlap == false) {
            rectangle insert_rec = rectangle(trans_x1, trans_y1, trans_x2, trans_y2);
            insert_rec.init_inf=std_rec.init_inf;
            asb_rec.inserted_recs.push_back(insert_rec);
            for (int i = trans_x1; i <= trans_x2; i++) {
                for (int j = trans_y1; j <= trans_y2; j++) {
                    asb_rec.occu_map[i][j] = 1;
                }
            }
            double area_sum = 0;
            area_sum += asb_rec.poly_outer.get_rectangle(asb_rec.poly_outer.allVertrx).area;
            if (asb_rec.poly_inner.allVertrx.size() != 0) {
                area_sum += asb_rec.poly_inner.get_rectangle(asb_rec.poly_inner.allVertrx).area;
            }
            for (const rectangle& rec : asb_rec.inserted_recs) {
                area_sum += rec.area;
            }
            asb_rec.rate = asb_rec.area / area_sum;
            if (asb_rec.rate < 1) {
                asb_rec.if_better = true;
            }
            asb_rec.occu_rate = asb_rec.occu_rate + ((double)asb_rec.inserted_recs.back().area / asb_rec.area);
            return true;
        }
        return false;
    }
    static void init_occu_map(Assembled_rec& temp) {
        for (int i = 0; i <= temp.x2; i++) {
            vector<int> occu_temp;
            for (int j = 0; j <= temp.y2; j++) {
                occu_temp.push_back(0);
            }
            temp.occu_map.push_back(occu_temp);
        }
        const vector<rectangle>& inner_recs = temp.poly_inner.allRect;
        for (const rectangle& temp_rec : inner_recs) {
            for (int i = temp_rec.x1; i <= temp_rec.x2; i++) {
                for (int j = temp_rec.y1; j <= temp_rec.y2; j++) {
                    temp.occu_map[i][j] = 1;
                }
            }
        }
        const vector<rectangle>& outer_recs = temp.poly_outer.allRect;
        for (const rectangle& temp_rec : outer_recs) {
            for (int i = temp_rec.x1; i <= temp_rec.x2; i++) {
                for (int j = temp_rec.y1; j <= temp_rec.y2; j++) {
                    temp.occu_map[i][j] = 1;
                }
            }
        }
    }
    static Assembled_rec try_3_times(const combin_index& index, vector<polygon>& poly_vec) {
        static int sand_plus = 0;
        Assembled_rec temp_asb;
        Assembled_rec best_asb = Assembled_rec();
        for (int n = 0; n < 3; n++) {
            srand(time(0) + sand_plus);
            random_shuffle(poly_vec[index.com_1_index].allVertrx.begin(), poly_vec[index.com_1_index].allVertrx.end());
            random_shuffle(poly_vec[index.com_2_index].allVertrx.begin(), poly_vec[index.com_2_index].allVertrx.end());
            sand_plus++;
            poly_vec[index.com_1_index].toRepr2();
            poly_vec[index.com_1_index].get_blank_Repr();
            poly_vec[index.com_2_index].toRepr2();
            poly_vec[index.com_2_index].get_blank_Repr();
            temp_asb = get_best_Assembled_rec(index, poly_vec);
            if (best_asb.if_success == false) {
                best_asb = temp_asb;
            }
            else {
                if (temp_asb.if_success == true) {
                    if (best_asb.area > temp_asb.area) {
                        best_asb = temp_asb;
                    }
                }
            }
        }
        return best_asb;
    }
    static int get_asb_vec_areasum(const vector<Assembled_rec>& asb_vec) {
        int area_sum = 0;
        for (const Assembled_rec& temp_asb : asb_vec) {
            area_sum += temp_asb.area;
        }
        return area_sum;
    }
    static bool judge_if_equal(const combin_index& exist, const combin_index& temp) {
        if (exist.com_1_index == temp.com_1_index || exist.com_1_index == temp.com_2_index || exist.com_2_index == temp.com_1_index || exist.com_2_index == temp.com_2_index) {
            return true;
        }
        return false;
    }
    static bool judge_if_equal_1(const combin_index& exist, const combin_index& temp) {
        if (exist.com_1_index == temp.com_1_index&&exist.com_2_index == temp.com_2_index) {
            return true;
        }
        return false;
    }
    static bool judge_if_repeat(const vector<combin_index>& group, const combin_index& temp, bool flag = false) {
        if (group.empty()) {
            return false;
        }
        for (combin_index exist : group) {
            if (flag == false) {
                if (judge_if_equal(exist, temp)) {
                    return true;
                }
            }
            else {
                if (judge_if_equal_1(exist, temp)) {
                    return true;
                }
            }
        }
        return false;
    }
    static bool judge_if_2d_repeat(const vector<combin_index>& group_1, const vector<combin_index>& group_2) {
        int flag = 0;
        for (int i = 0; i < group_1.size(); i++) {
            if (judge_if_repeat(group_2, group_1[i], true))
                flag++;
        }
        if (flag == group_1.size()) {
            return true;
        }
        return false;
    }
    static bool judge_if_3d_repeat(const vector<vector<combin_index>>& allgroups, const vector<combin_index>& group) {

        for (int i = 0; i < allgroups.size(); i++) {
            if (judge_if_2d_repeat(allgroups[i], group)) {
                return true;
            }
        }
        return false;
    }
    static void getgroups(vector<vector<combin_index>>& allgroups, vector<combin_index>& group, int size) {
        if (group.size() == size / 2 && !judge_if_3d_repeat(allgroups, group)) {
            allgroups.push_back(group);
            return;
        }
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (!judge_if_repeat(group, { i,j })) {
                    group.push_back({ i,j });
                    getgroups(allgroups, group, size);
                    group.pop_back();
                }
            }
        }

    }
    static Assembled_rec get_best_Assembled_rec(const combin_index& com_index, vector<polygon>& poly_vec) {
        const Assembled_rec& asb_rec_1 = get_rota_overturn_Assembled_rec(poly_vec[com_index.com_1_index], poly_vec[com_index.com_2_index]);
        const Assembled_rec& asb_rec_2 = get_rota_overturn_Assembled_rec(poly_vec[com_index.com_2_index], poly_vec[com_index.com_1_index]);
        return get_better(asb_rec_1, asb_rec_2);
    }
    static Assembled_rec get_better(const Assembled_rec& asb_rec_1, const Assembled_rec& asb_rec_2) {
        if (asb_rec_1.if_success == false && asb_rec_2.if_success == false) {
            return asb_rec_1;
        }
        else if (asb_rec_1.if_success == true && asb_rec_2.if_success == false) {
            return asb_rec_1;
        }
        else if (asb_rec_1.if_success == false && asb_rec_2.if_success == true) {
            return asb_rec_2;
        }
        else {
            if (asb_rec_1.area < asb_rec_2.area) {
                return asb_rec_1;
            }
            return asb_rec_2;
        }
    }
    static void do_overturn(const double& std, vector<pos>& pos_vec, const int& choice) {
        if (choice == 0) {
            for (pos& temp_pos : pos_vec) {
                temp_pos.x = std + (std - temp_pos.x);
            }
        }
        else {
            for (pos& temp_pos : pos_vec) {
                temp_pos.y = std + (std - temp_pos.y);
            }
        }
    }
    static Assembled_rec get_rota_overturn_Assembled_rec(const polygon& outer, polygon inner) {
        Assembled_rec rotation_best;
        Assembled_rec temp;
        for (int i = 0; i < 6; i++) {
            if (i == 0) {
                rotation_best = get_Assembled_rec(outer, inner);
                continue;
            }
            else if (i <= 3 && i >= 1) {
                const rectangle& temp_rec = polygon::get_rectangle(inner.allVertrx);
                Assembled_rec::clockwise_rotation_90(pos(temp_rec.x_mid, temp_rec.y_mid), inner.allVertrx);
                temp = get_Assembled_rec(outer, inner);
            }
            else if (i == 4) {
                const rectangle& temp_rec = polygon::get_rectangle(inner.allVertrx);
                vector<pos> store = inner.allVertrx;
                do_overturn(temp_rec.x_mid, inner.allVertrx, 0);
                temp = get_Assembled_rec(outer, inner);
                inner.allVertrx = store;
            }
            else {
                const rectangle& temp_rec = polygon::get_rectangle(inner.allVertrx);
                vector<pos> store = inner.allVertrx;
                do_overturn(temp_rec.y_mid, inner.allVertrx, 1);
                temp = get_Assembled_rec(outer, inner);
                inner.allVertrx = store;
            }
            if (rotation_best.if_success == false) {
                rotation_best = temp;
            }
            else {
                if (temp.if_success == true) {
                    if (rotation_best.area > temp.area) {
                        rotation_best = temp;
                    }
                }
            }
        }
        return rotation_best;
    }
    static Assembled_rec get_Assembled_rec(const polygon& outer, const polygon& inner) {
        Assembled_rec best_rec = Assembled_rec();
        for (int i = 0; i < outer.all_blank_Rect.size(); i++) {
            for (int j = 0; j < inner.allRect.size(); j++) {
                if (if_can_put(outer.all_blank_Rect[i], inner.allRect[j])) {
                    Assembled_rec temp_rec = get_best_pos_asb_rec(outer, inner, i, j);
                    if (best_rec.if_success == false) {
                        best_rec = temp_rec;
                    }
                    else {
                        if (temp_rec.if_success == true) {
                            if (best_rec.area > temp_rec.area) {
                                best_rec = temp_rec;
                            }
                        }

                    }
                }
            }
        }
        return best_rec;
    }
    static Assembled_rec get_best_pos_asb_rec(polygon outer, polygon inner, int i, int j) {
        int std_x, std_y, rec_x, rec_y;
        Assembled_rec best_pos_asb_rec = Assembled_rec();
        for (int m = 0; m < 4; m++) {
            switch (m) {
            case 0:
                std_x = outer.all_blank_Rect[i].x1;
                std_y = outer.all_blank_Rect[i].y1;
                rec_x = inner.allRect[j].x1;
                rec_y = inner.allRect[j].y1;
                break;
            case 1:
                std_x = outer.all_blank_Rect[i].x1;
                std_y = outer.all_blank_Rect[i].y2;
                rec_x = inner.allRect[j].x1;
                rec_y = inner.allRect[j].y2;
                break;
            case 2:
                std_x = outer.all_blank_Rect[i].x2;
                std_y = outer.all_blank_Rect[i].y2;
                rec_x = inner.allRect[j].x2;
                rec_y = inner.allRect[j].y2;
                break;
            case 3:
                std_x = outer.all_blank_Rect[i].x2;
                std_y = outer.all_blank_Rect[i].y1;
                rec_x = inner.allRect[j].x2;
                rec_y = inner.allRect[j].y1;
                break;
            }
            polygon::std_pos_vec(inner.allVertrx, std_x, std_y, rec_x, rec_y);
            vector<pos> allpos;
            allpos.insert(allpos.end(), inner.allVertrx.begin(), inner.allVertrx.end());
            allpos.insert(allpos.end(), outer.allVertrx.begin(), outer.allVertrx.end());
            rectangle tool_rec = polygon::get_rectangle(allpos);
            polygon::std_pos_vec(inner.allVertrx, 0, 0, tool_rec.x1, tool_rec.y1);
            polygon::std_pos_vec(outer.allVertrx, 0, 0, tool_rec.x1, tool_rec.y1);
            inner.toRepr2();
            inner.get_blank_Repr();
            outer.toRepr2();
            outer.get_blank_Repr();
            if (if_overlap(outer.allRect, inner.allRect, tool_rec.x2 - tool_rec.x1, tool_rec.y2 - tool_rec.y1)) {
                continue;
            }
            else {
                Assembled_rec temp_rec = Assembled_rec(outer, inner);
                if (best_pos_asb_rec.if_success == false) {
                    best_pos_asb_rec = temp_rec;
                }
                else {
                    if (best_pos_asb_rec.area > temp_rec.area) {
                        best_pos_asb_rec = temp_rec;
                    }
                }

            }
        }
        return best_pos_asb_rec;
    }
    static bool if_overlap(const vector<rectangle>& exist_rec_vec, const vector<rectangle>& new_rec_vec, int max_x, int max_y) {
        vector<vector<int>> record_rec(max_y + 1, vector<int>(max_x + 1, 0));
        for (const rectangle& exist_rec : exist_rec_vec) {
            for (int i = exist_rec.x1; i <= exist_rec.x2; i++) {
                for (int j = exist_rec.y1; j <= exist_rec.y2; j++) {
                    record_rec[j][i] = 1;
                }
            }
        }
        for (const rectangle& new_rec : new_rec_vec) {
            for (int i = new_rec.x1; i <= new_rec.x2; i++) {
                for (int j = new_rec.y1; j <= new_rec.y2; j++) {
                    if (record_rec[j][i] == 1) {
                        record_rec[j][i] = 2;
                    }
                }
            }
        }
        for (int i = 0; i < record_rec.size(); i++) {
            for (int j = 0; j < record_rec[i].size(); j++) {
                if (record_rec[i][j] == 2) {
                    if ((i + 1 < record_rec.size() && record_rec[i + 1][j] == 2) && (j + 1 < record_rec[i].size() && record_rec[i][j + 1] == 2)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    static bool if_can_put(const rectangle& outer, const rectangle& inner) {
        if (((outer.x2 - outer.x1) >= (inner.x2 - inner.x1)) && ((outer.y2 - outer.y1) >= (inner.y2 - inner.y1))) {
            return true;
        }
        return false;
    }



};
class Concave : public rectangle{
public:
    vector<pos> allVertrx;
    Concave(const Concave& temp_concave){
        this->allVertrx=temp_concave.allVertrx;
        this->index = temp_concave.index;
        this->delayConstru(temp_concave.x1, temp_concave.y1,temp_concave.x2, temp_concave.y2);
        this->init_inf=temp_concave.init_inf;
    }
    Concave(const polygon& temp_polygon){
        this->allVertrx=temp_polygon.allVertrx;
        this->init_inf=temp_polygon.init_inf;
        const rectangle& temp_rec=polygon::get_rectangle(this->allVertrx);
        this->delayConstru(temp_rec.x1, temp_rec.y1,temp_rec.x2, temp_rec.y2);
    }
    bool operator ==(const Concave& p) const {
        if (p.init_inf==this->init_inf) {
            return true;
        }
        return false;
    }
    void write_file(fstream& file) {
        const rectangle& temp = polygon::get_rectangle(this->allVertrx);
        if ((((x2 - x1) != (temp.x2 - temp.x1)) && ((x2 - x1) == (temp.y2 - temp.y1))) && (((y2 - y1) != (temp.y2 - temp.y1)) && ((y2 - y1) == (temp.x2 - temp.x1)))){
            Assembled_rec::clockwise_rotation_90(pos(temp.x1, temp.y1), this->allVertrx);
        }
        const rectangle& temp_temp = polygon::get_rectangle(this->allVertrx);
        polygon::std_pos_vec(this->allVertrx, x1, y1, temp_temp.x1, temp_temp.y1);
        string result;
        result += "In Polygon:\n";
        result+=this->init_inf+"\n";
        result += "Out Polygon:\n";
        for (int i = 0; i < this->allVertrx.size(); i++) {
            result += "(" + to_string(this->allVertrx[i].x) + "," + to_string(this->allVertrx[i].y) + ")";
            if (i == this->allVertrx.size() - 1) {
                result += "\n";
            }
        }
        file << result;
    }
    int get_occu_area() {
        return this->area;
    }
    rectangle* get_copy() {
        return new Concave(*this);
    }
};

